from collections import deque
import time


class Dog:
    def __init__(self, name):
        self.name = name
        self.create_time = 0


class Cat:
    def __init__(self, name):
        self.name = name
        self.create_time = 0


class DogCatQueue:
    def __init__(self):
        self.dog_queue, self.cat_queue = deque(), deque()

    def enque(self, animal):
        animal.create_time = time.time()
        if isinstance(animal, Dog):
            self.dog_queue.append(animal)
        elif isinstance(animal, Cat):
            self.cat_queue.append(animal)

    def deque_cat(self):
        return self.cat_queue.popleft()

    def deque_dog(self):
        return self.dog_queue.popleft()

    def deque_any(self):
        if not self.dog_queue:
            return self.deque_cat()
        if not self.cat_queue:
            return self.deque_dog()
        mycat, mydog = self.cat_queue[0], self.dog_queue[0]
        if mycat.create_time < mydog.create_time:
            return self.deque_cat()
        else:
            return self.deque_dog()


tomcat = Cat('Tom')
bobdog = Dog('Bob')
lilycat = Cat('Lily')
kencat = Cat('Ken')
johndog = Dog('John')

myque = DogCatQueue()
myque.enque(tomcat)
time.sleep(0.5)
myque.enque(bobdog)
time.sleep(0.5)
myque.enque(lilycat)
time.sleep(0.5)
myque.enque(kencat)
time.sleep(0.5)
myque.enque(johndog)

ans = myque.deque_dog()
print(ans.name)
